package com.zhang;

/**
 * @author ZhangJiXin
 * @Description UnionFind -- QU(快速合并)优化
 * @date 2021/4/30 9:52
 */
public  class UnionFind_QU extends UnionFind{

    public UnionFind_QU(int capacity) {
       super(capacity);
    }

    /**
     * 查找当前元素指向的根节点 是否一样
     * 如果一样 说明当前元素就是根节点
     * 如果不一样 就将指向的元素 当作当前元素再进行查找
     * @Author ZhangJiXin
     * @Date 2021/4/30 11:26
     * @param v:
     * @return: int
     */
    @Override
    public int find(int v){
        rangeCheck(v);
        while (v != parents[v]){
            v = parents[v];
        }
        return v;
    }

    /**
     * 快速合并实现的复杂度是 O(longN)
     * 它是通过将左边元素的根元素 指向 右边元素的根节点
     * 注意：这样有一个弊端 可能会出现树退化成链表的情况 从而使查询复杂度变成O(N)
     * @Author ZhangJiXin
     * @Date 2021/4/30 11:21
     * @param v1:
     * @param v2:
     * @return: void
     */
    @Override
    public void union(int v1, int v2){
        int v1Root = find(v1);
        int v2Root = find(v2);
        if (v1Root == v2Root){
            return;
        }
        parents[v1Root] = v2Root;
    }

}
